\documentclass[11pt]{article}
\addtolength{\oddsidemargin}{-.5in}
\addtolength{\evensidemargin}{-.5in}
\addtolength{\textwidth}{1in}
\addtolength{\topmargin}{-.5in}
\addtolength{\textheight}{1in}
%\usepackage{palatino}
\usepackage{amsmath, amsthm, amssymb}
\newcommand{\PR}{\mathrm{Pr}}
\newcommand{\M}{\mathcal{M}}
\newcommand{\C}{\mathcal{C}}
\newcommand{\K}{\mathcal{K}}
\newcommand{\D}{\mathcal{D}}
\newcommand{\assert}{\stackrel{?}{=}}


\begin{document}
\begin{center}
\textbf{\bf CS555 Class Project, Spring 2011}\\
\vspace{0.05in}
{\Large\bf System for electronic voting}\\
\vspace{0.075in}
{\bf Dasarath Weeratunge and Phillip Hayes Jr.}
\rule{\textwidth}{.005in}
\end{center}

\flushleft

\section{Protocol}

This section describes the protocol that we implement. This protocol is described by Qi He and Zhongmin Su
in `A New Practical Secure e-Voting Scheme'.

\begin{enumerate}
\item
CTF has a list of $\mathrm{username}, h(\mathrm{password})$ \footnote{$h$ indicates hash function.}
CTF chooses public/private key pair $E_c,D_c$ and publishes a list of usernames of all eligible voters.
\item
Each voter selects a public/private key pair $E_v, D_v$ and a random number $R$.
$E_v$ is called tallying key.
Let $X = E_c(R) \times h(E_v)$. A voter sends to CTF \\
$M_1=\{X, E_c(\mathrm{username}, \mathrm{password}, h(X))\}$.
If the voter is eligible to vote, CTF replies with $M_2=D_c(E_c(R) \times h(E_v))=R \times D_c(h(E_v))$.
Each voter computes $M_2/R=D_c(h(E_v))$ and asserts $E_c(M_2/R) \assert h(E_v)$.
\item
At the end of the registration period, CTF publishes a list of usernames of voters who have registered for the election.
\item
Each voter sends to CTF, $M_3=\{E_v, D_v(D_c(h(E_v)))\}$. CTF asserts \\
$E_c(E_v(D_v(D_c(h(E_v))))) \assert h(E_v)$.
%(what if $M_3 \assert \{E_v, D_c(h(E_v)), D_v(h(D_c(h(E_v))))\}$ ? this allows modulus of CTF and voter to be of
%the same size)
\item
At the end of the tallying key submission period, CTF publishes a list of all tallying keys it has has received.
\item
Each voter selects a secret key $K_v$ and sends to CTF,
$M_4=\{E_v, K_v(B)), D_v(h(K_v(B)))\}$.\\
CTF asserts that $E_v(D_v(h(K_v(B)))) \assert h(K_v(B))$.
\item
Until the voting is concluded, a voter wishing to change his/her vote can resend $M_4$.
\item
At the end voting period, CTF publishes a list of all encrypted votes it received against corresponding tallying keys.
\item
Each voter sends to CTF $M_5=\{E_v, K_v, D_v(h(K_v))\}$. CTF asserts $E_v(D_v(h(K_v))) \assert h(K_v)$
and uses $K_v$ to decrypt the ballots and count the votes.
\item
At end of the election, for each $B$, CTF publishes\\
 $\{E_v, K_v, D_v(h(K_v)), D_v(h(K_v(B))), D_v(D_c(h(E_v)))\}$
for universal verification.
\end{enumerate}

\newpage
\section{Implementation}

In this section, we describe our implementation of above protocol.

\subsection{Programs}

\begin{enumerate}
\item
{\bf server:} This program performs the actions of the CTF.
\item
{\bf server-admin:} This program allows one to inform the CTF (i.e. server program), when to begin
and end different phases of the election.
\item
{\bf client:} This program allows a voter to participate in the election.
\item
{\bf genuid:} This is a tool for generating usernames and passwords for each voter.
\end{enumerate}

\subsection{Usage}

\begin{enumerate}
\item
We begin by generating a password for each voter. We use the {\bf genuid} tool for this.
Assume we have 100 voters. Then the following command generates 100 different passwords.
The voters are assigned usernames 0 to 99.

\begin{verbatim}
./genuid 100
\end{verbatim}

The genuid program creates a file named {\bf mypasswd} listing each for each username, the 
SHA1 hash value of password. Additionally, each password is stored in a separate file under
the corresponding username.

\item
Next start the {\bf server}. When we start the server we need to specify the number of
choices (say $N$) voters have when voting. These choices are identified by numbers 0 through $N-1$.
If we have 7 choices, start the server like below:

\begin{verbatim}
./server --choices=7
\end{verbatim}

Once started, the server program waits for connections from voters (client program) 
or server adminisrator (server-admin tool). As part of starting up, the server creates CTF's
public and private keys and loads all password infomation in file mypasswd.

\item
When the server has started up, it does not accept requests by voters to register. To tell
server to begin the registration phase of the election, we do the following:

\begin{verbatim}
./server-admin --reg
\end{verbatim}

At this point the server will publish a list of usernames of all eligible voters in file {\bf progress}.
This file could be made available online by the user of a web server.

\item
During registration phase each voter uses the client program to register with CTF.
The voter with username 3, will use his password stored in file `3' by genuid program to
register with CTF in the following way. The option --keyfile specifies the file used
by the client program to store the client's tallying key ($E_v$), the related private key ($D_v$),
the secret key $K_v$ and tallying key signed by CTF $D_c(h(E_v))$. At the end of this step,
all of the above data except $K_v$ will be added to file K3.

\begin{verbatim}
./client --uid=3 --passwd=`cat 3` --keyfile=K3 --reg
\end{verbatim}

\item
At the end of the registration period, the administrator does the following.

\begin{verbatim}
./server-admin --tally-keys
\end{verbatim}

This concludes the registration phase and starts the tallying key submission phase.
The server program also updates the progress with the usernames of all voters who have registered.

\item
To submit tallying key chosen during registration and signed by CTF, each voter again uses
the client program in the following way.

\begin{verbatim}
./client --keyfile=K3 --tally-key
\end{verbatim}

\item
At the end of the tallying key submission period, the administrator does the following.

\begin{verbatim}
./server-admin --vote
\end{verbatim}

This concludes the tallying key submission phase and starts the voting phase.
The server program also updates the progress with the all tallying keys it has received.

\item
Each voter uses the client to vote in the following way. Say the voter is voting for choice 5 (i.e. ballot)

\begin{verbatim}
./client --keyfile=K3 --vote=5
\end{verbatim}

\item
At the end of the voting period, the administrator does the following.

\begin{verbatim}
./server-admin --tally
\end{verbatim}

This concludes the voting period and allows voters to submit their secret keys which the CTF
consequently uses to decrypt their ballots. The CTF also updates the progress file with all
the encrypted ballots it received against their respective tallying keys.

\item
To submit the secret key to CTF the voter uses the client in the following way.

\begin{verbatim}
./client --keyfile=K3 --tally
\end{verbatim}

\item
To conclude the election and publish final tally, the administrator does the following.

\begin{verbatim}
./server-admin --done
\end{verbatim}

In response, the server program counts all decrypted ballots, prints out the final tally,
updates the progress file with decrypted ballot against each tallying key and terminates itself.


\end{enumerate}

\subsection{Source code}

We have hosted our implementation online using Google Source. Anyone may checkout a copy
anonymously using the following command.

\begin{verbatim}
svn checkout http://cs555-electronic-voting.googlecode.com
	/svn/trunk/ cs555-electronic-voting-read-only
\end{verbatim}

This project has been implemented in C/C++ using GCC. We chose C/C++ for efficiencly
and C++ over C since it allows us to use C++ Standard Template Library (STL).
To perform cryptographic operations such as RSA, AES, SHA1 we use OpenSSL libcrypto
library. For performing arithmetic on large integers we use the same BIGNUM API used
in libcrypto. We also make use of libcrypto's cryptographically secure pseudo-random number generator
API for generating random numbers. We use OpenSSL BIO network API for communicating between
different programs: (e.g. server and client). The links to these APIs are provided below.

\begin{verbatim}
http://www.openssl.org/docs/crypto/crypto.html
http://www.openssl.org/docs/crypto/bn.html
http://www.openssl.org/docs/crypto/rand.html
http://www.openssl.org/docs/crypto/bio.html
\end{verbatim}

The source tree has the following files:

\begin{center}
\begin{tabular}{ll}
\hline
project.h & project wide header file with global definitions. \\
project.cpp & routines common to all tools in the project. \\
server.cpp & CTF \\
server-admin.cpp & tool to administer CTF. \\
client.cpp & the front end used by voter. \\
genuid.cpp & tool for generating passwords. \\
Makefile & build script.\\
\hline
\end{tabular}
\end{center}


\section{Contribution}

With this document includes a listing of the source code program, the algorithm that was design to create the program and the
document which describes it, the results of timing experiments to show how fast our program runs and test data and results with is
incorporated into a text file.  Dasarath is in charge for setting up the protocol, performing the calculations of signing keys for
voters, design key be randomized during voting processing, and out the results to an text file as well as the console. Phillip is
in charge of commenting the source codes and creating scripts to test the system and debugging for any errors that were found. 

\section{Testing}

\subsection{Regression testing}

The following script checks for error conditions that can arise
during an election. It uses 13 different voters who act out different scenarios.

\begin{center}
\begin{tabular}{lp{4in}}
\hline
\hline
K0 & This voter votes before the election has never begun. Hence it does not
     receive any response from CTF. But it continues to vote using an empty keyfile.
     we mainly use it to test whether our client can properly detect this error and
     no crash. \\
\hline
K1 & In the voting phase, K1 votes multiple times. We use K1 to check whether CTF counts
     only the last ballot in such cases.\\
\hline
K2 & This voter drops out of the election after submitting the tallying key. (i.e. He
     completes the registration process successfully but does not vote.\\
\hline
K3 & This voter submits hit tallying key twice and consequently CTF blocks his key.
     In the CTF's progress report the tallying key shows up as disabled. He continues
     to participate in the election but CTF discards his votes. \\
\hline
K4 & Does everything by the book! K4 is a control experiment. Since the final result has
     two ballots that were marked 3, we see that both K1's and K4's ballots have been
     properly counted.\\
\hline
K2000 & A voter who's username is not in the list of eligible voters. Rejected by CTF.\\
\hline
K5 & Uses wrong password. Rejected by CTF.\\
\hline
K6 & Does not send his tallying key in the tallying key submission phase. Hence his
    ballot is not counted. \\
\hline
K7 & Will not vote. But still tries to send his secret key during the last phase.
     A voter who does not vote is not in possession of a secret key (its just not there in his
     keyfile). We use K7 to test that our client doesn't crash when this happens.\\
\hline
K8 & Will not reveal his secret key. So his ballot is not counted.\\
\hline
K9 & Will send his secret key multiple times. This is not a problem.\\
\hline
K10 & Casts an illegal ballot (-1). This only shows up in the last phase when the ballots are revealed.\\
\hline
K11 & Casts an illegal ballot (1000). This only shows up in the last phase when the ballots are revealed.\\
\hline
K12 & Like K0, K12 also first tries to register before registration phase has begun. But unlike K0, he registers
      again after registration begins. Thus K12 is able to successfully participate in the election.\\
\hline
\hline
\end{tabular}
\end{center}

\newpage

{\small
\begin{verbatim}
choices=7
cd TEST
../genuid 30
gnome-terminal --command="bash -c '../server --choices=$choices; echo hit ENTER...; read'"
sleep 2
# this voter tries to register before election has begun this attempt will fail.
# however he can register later without any problem again. To show this we
# have K0 who will not register and K12 who will and continue to successfully
# participate in the election.
../client --uid=0 --passwd=`cat 0` --keyfile=K0 --reg
../client --uid=12 --passwd=`cat 12` --keyfile=K12 --reg
sleep 1
../server-admin --reg
sleep 1
# try agin. this time K12 will succeed.
../client --uid=12 --passwd=`cat 12` --keyfile=K12 --reg
# these 4 clients will be able to successully register
../client --uid=1 --passwd=`cat 1` --keyfile=K1 --reg
../client --uid=2 --passwd=`cat 2` --keyfile=K2 --reg
../client --uid=3 --passwd=`cat 3` --keyfile=K3 --reg
../client --uid=4 --passwd=`cat 4` --keyfile=K4 --reg
# provide bad usernames and passwords both will not be able to get through
../client --uid=2000 --passwd=`cat 3` --keyfile=K2000 --reg
../client --uid=5 --passwd=`cat 41` --keyfile=K5 --reg
# try to register again, should be rejected but will still 
# be able to vote due to successful registration earlier.
../client --uid=4 --passwd=`cat 4` --keyfile=K4XXX --reg
# this voter will not send his tally key
../client --uid=6 --passwd=`cat 6` --keyfile=K6 --reg
# this voter will not vote
../client --uid=7 --passwd=`cat 7` --keyfile=K7 --reg
# will not send his secret key
../client --uid=8 --passwd=`cat 8` --keyfile=K8 --reg
# will send his secret key multiple times
../client --uid=9 --passwd=`cat 9` --keyfile=K9 --reg
# will cast illegal ballots
../client --uid=10 --passwd=`cat 10` --keyfile=K10 --reg
../client --uid=11 --passwd=`cat 11` --keyfile=K11 --reg

# the following will show up as registered to vote in progress:
# 1 2 3 4 6 7 8 9 10 11 12
# note that 0, 5 and 2000 are not listed.

sleep 1
../server-admin --tally-keys
sleep 1
# bad keyfile, should not crash
../client --keyfile=K0 --tally-key
# let's try a key conflict
# now this key (K3) will be blocked
../client --keyfile=K3 --tally-key
../client --keyfile=K3 --tally-key
# all the rest will work again without problem.
../client --keyfile=K1 --tally-key
../client --keyfile=K2 --tally-key
../client --keyfile=K4 --tally-key
# K6 is not providing his tallying key
../client --keyfile=K7 --tally-key
../client --keyfile=K8 --tally-key
../client --keyfile=K9 --tally-key
../client --keyfile=K10 --tally-key
../client --keyfile=K11 --tally-key
../client --keyfile=K12 --tally-key

# there will be 10 tallying keys with 1 disabled (that of K3)
# K0 does not have a key to provide.

sleep 1
../server-admin --vote
sleep 1

# try using bad keyfile, just to see that we do not throw up
../client --keyfile=K0 --vote=0
# a voter who cannot make up his mind, only the last vote counted.
../client --keyfile=K1 --vote=0
../client --keyfile=K1 --vote=1
../client --keyfile=K1 --vote=2
../client --keyfile=K1 --vote=3
# K2 drops out
# K3 is blocked so his vote will be rejected.
../client --keyfile=K3 --vote=3
# bad ballots, only 7 choices available
../client --keyfile=K10 --vote=1000
../client --keyfile=K11 --vote=-1
# try to vote without sending the tallying key.
../client --keyfile=K6 --vote=4
# K7 will not vote but will try to send the voting key and fail.
# voting key is only present in the key file if you vote.
# the following will have no problem.
../client --keyfile=K4 --vote=3
../client --keyfile=K8 --vote=4
../client --keyfile=K9 --vote=5
../client --keyfile=K12 --vote=5

# at the end of this phase two more tallying keys show up as
# having invalid IV,Kv(B)'s (K2 and K7). K3 also has an invalid
# vote since he is blocked. Note that though K10 and K11 cast
# illegal ballots their encrypted ballots are considered valid.

sleep 1
../server-admin --tally
sleep 1
# try using bad keyfile
../client --keyfile=K0 --tally
../client --keyfile=K1 --tally
# K3 is blocked
../client --keyfile=K3 --tally
../client --keyfile=K4 --tally
# try to again send the secret key without sending the tallying key
../client --keyfile=K6 --tally
# K7 does not have a voting key to send so will fail.
../client --keyfile=K7 --tally
# K8 won't send his secrety key.
# try sending the tally key multiple times no problem.
../client --keyfile=K9 --tally
../client --keyfile=K9 --tally
../client --keyfile=K9 --tally
../client --keyfile=K9 --tally
# K10 and K12 cast illegal ballots
../client --keyfile=K10 --tally
../client --keyfile=K11 --tally
# K12 no problem.
../client --keyfile=K12 --tally

# only the following voters will count at the end: K1(3), K4(3), K9(5), K12(5)

sleep 1
# its all done!
../server-admin --done

\end{verbatim}
}

The output of running the script is shown next. This is what is saved in the file ``progress''
by CTF after the election.


{\small
\begin{verbatim}
Tue Apr 12 10:49:24 EDT 2011

eligible voters: (username)
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


registered voters: (username)
1
2
3
4
6
7
8
9
10
11
12


tallying keys received: (disabled, Ev, DvDchEv)
1, 3081A70281A100C3D90AA3BF8CF127DE91A93DACD41C0A920F7A1645C9FE3815C99

0, 3081A70281A100DBB5F96D3F65FF7EF9E0A02C98D948A48CC1D83065754E6EFB235

0, 3081A70281A100C4316E0423F8C19661F2A572ED340BDB073A028BB072F3F92AC78

0, 3081A70281A100B7FA828CE33737EC9643E0981055C283B65B3A6E42D6E8C1CEF9A

0, 3081A70281A100E0137E5BAF2733BA22F1F32C1449716087264B83DAC142C592006

0, 3081A70281A100A79CA213A2AD0FAD7FF58387C99F1B9E9732635496C9F8EDA2ED1

0, 3081A70281A100C8C935180100A0E1ACB57AF6AD10F94ECD22A407B39885CB3C9FD

0, 3081A70281A100D83A25675F344F36030B40D7FCA2E495032EFFF57C1CC078488E6

0, 3081A70281A100A85BACB8788497EB919BA416CD0AAFB4D55FD7A014BF29B1006C7

0, 3081A70281A100BA5C69EF6FE5F9B51D10C9F333C76D391F12F0056D2CC3BCC9014



votes received: (disabled, IVKvB_valid, Ev, DvhIVKvB, IVKvB)
1, 0, 3081A70281A100C3D90AA3BF8CF127DE91A93DACD41C0A920F7A1645C9FE3815

0, 1, 3081A70281A100DBB5F96D3F65FF7EF9E0A02C98D948A48CC1D83065754E6EFB

0, 0, 3081A70281A100C4316E0423F8C19661F2A572ED340BDB073A028BB072F3F92A

0, 1, 3081A70281A100B7FA828CE33737EC9643E0981055C283B65B3A6E42D6E8C1CE

0, 0, 3081A70281A100E0137E5BAF2733BA22F1F32C1449716087264B83DAC142C592

0, 1, 3081A70281A100A79CA213A2AD0FAD7FF58387C99F1B9E9732635496C9F8EDA2

0, 1, 3081A70281A100C8C935180100A0E1ACB57AF6AD10F94ECD22A407B39885CB3C

0, 1, 3081A70281A100D83A25675F344F36030B40D7FCA2E495032EFFF57C1CC07848

0, 1, 3081A70281A100A85BACB8788497EB919BA416CD0AAFB4D55FD7A014BF29B100

0, 1, 3081A70281A100BA5C69EF6FE5F9B51D10C9F333C76D391F12F0056D2CC3BCC9



tally: (disabled, K_valid, VOTE, Ev, DvhK, K)
1, 0, 0, 3081A70281A100C3D90AA3BF8CF127DE91A93DACD41C0A920F7A1645C9FE3

0, 1, 3, 3081A70281A100DBB5F96D3F65FF7EF9E0A02C98D948A48CC1D83065754E6

0, 0, 0, 3081A70281A100C4316E0423F8C19661F2A572ED340BDB073A028BB072F3F

0, 1, 3, 3081A70281A100B7FA828CE33737EC9643E0981055C283B65B3A6E42D6E8C

0, 0, 0, 3081A70281A100E0137E5BAF2733BA22F1F32C1449716087264B83DAC142C

0, 0, 0, 3081A70281A100A79CA213A2AD0FAD7FF58387C99F1B9E9732635496C9F8E

0, 1, 5, 3081A70281A100C8C935180100A0E1ACB57AF6AD10F94ECD22A407B39885C

0, 1, 1000, 3081A70281A100D83A25675F344F36030B40D7FCA2E495032EFFF57C1C

0, 1, -1, 3081A70281A100A85BACB8788497EB919BA416CD0AAFB4D55FD7A014BF29

0, 1, 5, 3081A70281A100BA5C69EF6FE5F9B51D10C9F333C76D391F12F0056D2CC3B

RESULTS:
0 - 0
1 - 0
2 - 0
3 - 2
4 - 0
5 - 2
6 - 0
rejected= 2, count_all= 6


\end{verbatim}
}


The {\bf RESULTS:} displays the final tally. First, CTF prints N lines of the form ``choice - count''
which tells the number of ballots that were cast for each choice. Next it displays, the number
of rejected ballots. A ballot may be rejected if its out of the range: $[0\ ..\ choices)$.
For example if there are only 7 choices ballots cast for choices -1 and 9 will be rejected.
Finally a tally of all legal ballots is displayed (count\_all).



\subsection{Timing Experiment}

To measure how fast our implementation works, we did the following experiment. This test
was done on an Intel Core 2 Due 2.26 GHz computer with 4 GB of RAM. The election we conducted
involved 1000 voters and 7 choices. The full listing of the test script is given below.
When moving from one phase of the election to a new phase we insert a delay of 1 sec.
The election concluded in 2 min. and 4 sec. and the results are shown at the end of the listing.
Most of the time is taken up by the voter registration phase since this involves each voter
generating 1280 bit RSA modulus. The results shown at the end indicate that all 1000 votes
have been correctly counted.

{\small
\begin{verbatim}
choices=7
cd TEST
N=1000
../genuid $N
gnome-terminal --command=
	"bash -c '../server --choices=$choices; echo hit ENTER...; read'"
sleep 2
../server-admin --reg
sleep 1
for ((i = 0; i < $N; i++)); do echo $i;
	../client --uid=$i --passwd=`cat $i` --keyfile=K$i --reg; done
sleep 1
../server-admin --tally-keys
sleep 1
for ((i = 0; i < $N; i++)); 
	do echo $i; ../client --keyfile=K$i --tally-key; done
sleep 1
../server-admin --vote
sleep 1
for ((i = 0; i < $N; i++));
do 
	echo $i
	../client --keyfile=K$i 
		--vote=$((`cat /dev/urandom|od -N1 -An -i` % $choices))
done
sleep 1
../server-admin --tally
sleep 1
for ((i = 0; i < $N; i++)); do 
	echo $i; ../client --keyfile=K$i --tally; done
sleep 1
../server-admin --done

real    2m4.367s
user    1m3.680s
sys     0m13.750s

RESULTS:
0 - 130
1 - 173
2 - 123
3 - 150
4 - 132
5 - 149
6 - 143
rejected= 0, count_all= 1000
\end{verbatim}
}


\subsection{Remote server/client}

We also conducted more or less the same experiment that we did for timing over the network in our Lab (LWSN 3133).
We ran the server (i.e. CTF), on aragorn.cs.purdue.edu:8081 and clients (the shell script) 
on one of the student laptops. Since its the same script we do not duplicate it here.
We just produce the output of the server at the end of the election and time it took for the experiment to
finish.

\begin{verbatim}
RESULTS:
0 - 152
1 - 144
2 - 152
3 - 130
4 - 135
5 - 133
6 - 154
7 - 0
8 - 0
9 - 0
10 - 0
11 - 0
12 - 0
13 - 0
14 - 0
15 - 0
16 - 0
17 - 0
18 - 0
rejected= 0, count_all= 1000

real    2m26.264s
user    1m10.850s
sys     0m16.560s
\end{verbatim}

\end{document}

